Skip to main content

Start Here

Here’s a list of algorithms that frequently come up in technical interviews, categorized by topic. These algorithms are essential for solving common LeetCode-style questions:

1. Sorting and Searching • Binary Search: Often used for problems involving sorted arrays, search ranges, or optimization. • Example: Find peak element, search in rotated sorted array. • Binary Search • Search in Rotated Sorted Array • Merge Sort and Quick Sort: Understanding sorting algorithms is useful for custom sorting problems. • Two-Pointer Technique: Used for sorted arrays, such as finding pairs or triplets that meet a condition.

- Example Problems:
    • [Two Sum II](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/)
    • [3Sum](https://leetcode.com/problems/3sum/)
• **Sliding Window**: Common in problems involving subarrays or substrings.
    - Example Problems:
        • [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
        • [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)

2. Greedy Algorithms • Activity Selection Problem: Used for interval scheduling problems.

    - Example Problems:
        • [Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/)
• **Huffman Encoding**: Useful for compression-related problems.
• **Kruskal’s Algorithm** and **Prim’s Algorithm**: To find Minimum Spanning Trees (MST).
    - Example Problems:
        • [Min Cost to Connect All Points](https://leetcode.com/problems/min-cost-to-connect-all-points/)

3. Dynamic Programming (DP) • Knapsack Variants: Classic DP problem (0/1 Knapsack, Unbounded Knapsack). • Example Problems: • Partition Equal Subset Sum • Coin Change • Longest Common Subsequence (LCS) and Longest Common Substring. • Example Problems: • Longest Common Subsequence • Subset Sum and Partition Problems. • Fibonacci Variants: Often seen in recursion to DP conversions. • Example: Climbing stairs, house robber problem. • Matrix-based DP: • Pathfinding: Minimum path sum, unique paths.

    - Example Problems:
        • [Unique Paths](https://leetcode.com/problems/unique-paths/)
        • [Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)

4. Graph Algorithms • Breadth-First Search (BFS): For shortest path, level order traversal. • Example Problems: • Number of Islands • Word Ladder • Depth-First Search (DFS): For traversals, connected components, backtracking. • Dijkstra’s Algorithm: Shortest path in weighted graphs. • Example Problems: • Network Delay Time • Bellman-Ford Algorithm: Shortest path with negative weights. • Union-Find (Disjoint Set Union): For connected components, cycle detection. • Example Problems: • Redundant Connection • Topological Sorting: Used in dependency problems like course scheduling.

    - Example Problems:
        • [Course Schedule](https://leetcode.com/problems/course-schedule/)

5. Tree Algorithms • Binary Tree Traversals: Inorder, Preorder, Postorder. • Example Problems: • Binary Tree Inorder Traversal • Binary Search Tree Operations: Insert, delete, search. • Lowest Common Ancestor (LCA): Common in tree-related questions. • Example Problems: • Lowest Common Ancestor of a Binary Tree • Balanced Tree Algorithms: AVL trees, Red-Black trees for maintaining balance. • Trie (Prefix Tree): Common in string matching and autocomplete problems. • Example Problems: • Implement Trie (Prefix Tree)

6. String Algorithms • KMP Algorithm: For pattern matching. • Example Problems: • Find the Index of the First Occurrence in a String • Rabin-Karp Algorithm: For substring search using hashing. • Z Algorithm: For pattern matching and string searches. • Manacher’s Algorithm: To find the longest palindromic substring. • Example Problems: • Longest Palindromic Substring • Rolling Hash: For substring problems and detecting duplicates.

7. Mathematics and Number Theory • Greatest Common Divisor (GCD) / Least Common Multiple (LCM): • Example Problems: • Greatest Common Divisor of Strings • Euclid’s Algorithm for GCD. • Modular Arithmetic: Used for cyclic problems and hash functions. • Sieve of Eratosthenes: For prime number generation. • Example Problems: • Count Primes • Fast Exponentiation: To handle large powers efficiently.

8. Backtracking • Permutations and Combinations: Generate all possibilities (e.g., N-Queens, Sudoku Solver).

    - Examples:
        • [Permutations](https://leetcode.com/problems/permutations/)
        • [Combination Sum](https://leetcode.com/problems/combination-sum/)
• **Subset Generation**: Used in power set or combinations problems.
• **Word Search**: Finding patterns in grids.
    - Example Problems:
        • [Word Search](https://leetcode.com/problems/word-search/)

9. Heap / Priority Queue Algorithms • Heap Sort: Often used for k-th largest/smallest element problems. • Example Problems: • Kth Largest Element in an Array • Dijkstra’s Algorithm: For shortest paths using a priority queue. • Median Finder: Using two heaps to maintain the median. • Example Problems: • Find Median from Data Stream

10. Bit Manipulation • Basic Bitwise Operations: AND, OR, XOR, shifts. • Subset Generation: Using binary representation. • Single Number Problems: Using XOR to find unique numbers. • Bitmask DP: Common in advanced problems involving states.

11. Miscellaneous • Divide and Conquer: For problems like maximum subarray (Kadane’s Algorithm). • Reservoir Sampling: For random selection in streaming data.

    - Example Problems:
        • [Linked List Random Node](https://leetcode.com/problems/linked-list-random-node/)
• **Two-Sum Variants**: Hash maps for sum problems.
• **Monotonic Stack**: For problems involving next greater/smaller element.
    • Example Problems:
        • [Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)
• **Prefix Sum and Difference Arrays**: Used in range queries.
    • Example: 
        - [Range Sum Query](https://leetcode.com/problems/range-sum-query-immutable/description/)
        • [Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)